/*
 * Copyright (c) 2011, Yawning <yawninglol at gmail.com>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *   * Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *
 *   * Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 *
 *   * Neither the name of the Mew Developers nor the
 *     names of its contributors may be used to endorse or promote products
 *     derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 */

package yawning.mew.sim;

public class SimulationEventQueue {
	static class Node {
		public Node(SimulationEvent ev) {
			mEv = ev;
		}

		SimulationEvent mEv;
		Node mPrev;
		Node mNext;
	}

	SimulationEventQueue() {
		mHead = mTail = null;
	}

	private Node mHead;
	private Node mTail;

	public final SimulationEvent first() {
		return mHead.mEv;
	}

	public final SimulationEvent pollFirst() {
		if (mHead != null) {
			Node p = mHead;

			mHead = mHead.mNext;
			if (mHead != null) mHead.mPrev = null; else mTail = null;

			p.mNext = null;
			if (p.mPrev != null) {
				throw new RuntimeException("Event: " + p.mEv + " head has a valid prev reference.");
			}

			return p.mEv;
		}

		return null;
	}

	public final void add(SimulationEvent ev) {
		Node q = ev.mQueueNode;

		if (q.mPrev != null || q.mNext != null) {
			throw new RuntimeException("Event ev: " + ev + " already in event queue.");
		}

		if (mHead == null) {
			// Add to head (Empty queue).
			mHead = q;
			mTail = q;
		} else if (mHead.mEv.compareTo(ev) > 0) {
			// Add to head.
			q.mNext = mHead;
			mHead.mPrev = q;
			mHead = q;
		} else if (mTail.mEv.compareTo(ev) <= 0) {
			// Add to tail.
			mTail.mNext = q;
			q.mPrev = mTail;
			mTail = q;
		} else {
			Node p = mHead.mNext;

			do {
				if (p.mEv.compareTo(ev) > 0) {
					// Add to middle.
					q.mNext = p;
					q.mPrev = p.mPrev;
					p.mPrev.mNext = q;
					p.mPrev = q;

					break;
				} else {
					if (p.mNext == null) {
						throw new RuntimeException("Event ev: " + ev + " mTail: " + mTail + " fast path should have triggered.");
					}

					p = p.mNext;
				}
			} while(true);	// This will break out, unless the queue is screwed up.
		}
	}

	public final void remove(SimulationEvent ev) {
		Node p = ev.mQueueNode;

		// Technically speaking I should throw a exception here, but I need to support this since
		// certain events call SimulationEvent.cancel() from the onTick() handler.
		if (p.mPrev == null && p.mNext == null && p != mHead) return;

		if (p == mHead) {
			// Remove from head.
			mHead = p.mNext;
			if (mHead != null) mHead.mPrev = null; else mTail = null;
		} else if (p.mNext == null) {
			// Remove from tail.
			p.mPrev.mNext = null;
			mTail = p.mPrev;
		} else {
			// General case.
			p.mPrev.mNext = p.mNext;
			p.mNext.mPrev = p.mPrev;
		}

		p.mNext = null;
		p.mPrev = null;
	}

	public final boolean isEmpty() {
		return (mHead == null);
	}
}
